/**
 * 
 */
package leetCode;

import java.util.ArrayList;

/**
 * @author zhong
 *
 */
public class knightDialer {
	public int knightDialer(int N) {
		ArrayList<int[]> prevs = new ArrayList<>(10);
		prevs.add(new int[] { 4, 6 });// 0
		prevs.add(new int[] { 8, 6 });
		prevs.add(new int[] { 7, 9 });
		prevs.add(new int[] { 8, 4 });
		prevs.add(new int[] { 3, 9, 0 });
		prevs.add(new int[] {});
		prevs.add(new int[] { 1, 7, 0 });
		prevs.add(new int[] { 2, 6 });// 7
		prevs.add(new int[] { 1, 3 });
		prevs.add(new int[] { 2, 4 });

		int mod = 1000000007;
		int[][] dp = new int[2][10];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 10; j++) {
				if (i == 0) {
					dp[0][j] = 1;
				} else {
					for (int prev : prevs.get(j)) {
						dp[i % 2][j] += dp[(i + 1) % 2][prev];
						dp[i % 2][j] %= mod;
					}
				}
			}
			dp[(i + 1) % 2] = new int[10];
		}
		int sum = 0;
		for (int i = 0; i < 10; i++) {
			sum += dp[(N - 1) % 2][i];
			sum %= mod;
		}
		return sum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int N = 3;
		System.out.println(new knightDialer().knightDialer(N));
	}

}
